Search Results

Documents authored by Deza, Arnaud


Document
Fast Matrix Multiplication Without Tears: A Constraint Programming Approach

Authors: Arnaud Deza, Chang Liu, Pashootan Vaezipoor, and Elias B. Khalil

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)


Abstract
It is known that the multiplication of an N × M matrix with an M × P matrix can be performed using fewer multiplications than what the naive NMP approach suggests. The most famous instance of this is Strassen’s algorithm for multiplying 2× 2 matrices in 7 instead of 8 multiplications. This gives rise to the constraint satisfaction problem of fast matrix multiplication, where a set of R < NMP multiplication terms must be chosen and combined such that they satisfy correctness constraints on the output matrix. Despite its highly combinatorial nature, this problem has not been exhaustively examined from that perspective, as evidenced for example by the recent deep reinforcement learning approach of AlphaTensor. In this work, we propose a simple yet novel Constraint Programming approach to find algorithms for fast matrix multiplication or provide proof of infeasibility otherwise. We propose a set of symmetry-breaking constraints and valid inequalities that are particularly helpful in proving infeasibility. On the feasible side, we find that exploiting solver performance variability in conjunction with a sparsity-based problem decomposition enables finding solutions for larger (feasible) instances of fast matrix multiplication. Our experimental results using CP Optimizer demonstrate that we can find fast matrix multiplication algorithms for matrices up to 3× 3 with R = 23 in a short amount of time.

Cite as

Arnaud Deza, Chang Liu, Pashootan Vaezipoor, and Elias B. Khalil. Fast Matrix Multiplication Without Tears: A Constraint Programming Approach. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{deza_et_al:LIPIcs.CP.2023.14,
  author =	{Deza, Arnaud and Liu, Chang and Vaezipoor, Pashootan and Khalil, Elias B.},
  title =	{{Fast Matrix Multiplication Without Tears: A Constraint Programming Approach}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.14},
  URN =		{urn:nbn:de:0030-drops-190518},
  doi =		{10.4230/LIPIcs.CP.2023.14},
  annote =	{Keywords: fast matrix multiplication, computer-assisted proofs, constraint programming, constraint satisfaction problem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail